/**
 * Created by forcht on 2018/5/16.
 */
public class Solution {
    public int minCut(String s) {
        int[] dp=new int[s.length()];
        boolean[][] p=new boolean[s.length()][s.length()];
        dp[0]=0;
        for(int i=1;i<s.length();i++){
            dp[i]=Integer.MAX_VALUE;
            for(int j=0;j<=i;j++){
                if(s.charAt(i)==s.charAt(j)&&(i-j<2||p[j+1][i-1])){
                    p[j][i]=true;
                    if(j==0) dp[i]=0;
                    else dp[i]=Math.min(dp[i],dp[j-1]+1);
                }
            }
        }
        return dp[s.length()-1];
    }

    public static void main(String[] args) {
        Solution solution=new Solution();
        System.out.println(solution.minCut("aaa"));
    }
}
